<h2>题目编号 : 277</h2>
<div style="color:#666;font-size:80%;">06 February 2010</div><br />
<div class="problem_content">
<p>
A modified Collatz sequence of integers is obtained from a starting value a<img src="" style="display:none;" alt="_(" /><sub>1</sub><img src="" style="display:none;" alt=")" /> in the following way:</p>
<p>
<var>a<img src="" style="display:none;" alt="_(" /><sub>n+1</sub><img src="" style="display:none;" alt=")" /></var> = <var>a<img src="" style="display:none;" alt="_(" /><sub>n</sub><img src="" style="display:none;" alt=")" /></var>/3 if <var>a<img src="" style="display:none;" alt="_(" /><sub>n</sub><img src="" style="display:none;" alt=")" /></var> is divisible by 3. We shall denote this as a large downward step, "D".</p>
<p>
<var>a<img src="" style="display:none;" alt="_(" /><sub>n+1</sub><img src="" style="display:none;" alt=")" /></var> = (4<var>a<img src="" style="display:none;" alt="_(" /><sub>n</sub><img src="" style="display:none;" alt=")" /></var> + 2)/3 if <var>a<img src="" style="display:none;" alt="_(" /><sub>n</sub><img src="" style="display:none;" alt=")" /></var> divided by 3 gives a remainder of 1. We shall denote this as an upward step, "U".
</p>
<p>
<var>a<img src="" style="display:none;" alt="_(" /><sub>n+1</sub><img src="" style="display:none;" alt=")" /></var> = (2<var>a<img src="" style="display:none;" alt="_(" /><sub>n</sub><img src="" style="display:none;" alt=")" /></var> - 1)/3 if <var>a<img src="" style="display:none;" alt="_(" /><sub>n</sub><img src="" style="display:none;" alt=")" /></var> divided by 3 gives a remainder of 2. We shall denote this as a small downward step, "d".
</p>


<p>
The sequence terminates when some <var>a<img src="" style="display:none;" alt="_(" /><sub>n</sub><img src="" style="display:none;" alt=")" /></var> = 1.
</p>
<p>
Given any integer, we can list out the sequence of steps.<br />
For instance if <var>a</var><img src="" style="display:none;" alt="_(" /><sub>1</sub><img src="" style="display:none;" alt=")" />=231, then the sequence {<var>a<img src="" style="display:none;" alt="_(" /><sub>n</sub><img src="" style="display:none;" alt=")" /></var>}={231,77,51,17,11,7,10,14,9,3,1} corresponds to the steps "DdDddUUdDD".
</p>
<p>
Of course, there are other sequences that begin with that same sequence "DdDddUUdDD....".<br />
For instance, if <var>a</var><img src="" style="display:none;" alt="_(" /><sub>1</sub><img src="" style="display:none;" alt=")" />=1004064, then the sequence is DdDddUUdDDDdUDUUUdDdUUDDDUdDD.<br />
In fact, 1004064 is the smallest possible <var>a</var><img src="" style="display:none;" alt="_(" /><sub>1</sub><img src="" style="display:none;" alt=")" /> <img src='images/symbol_gt.gif' width='10' height='10' alt='&gt;' border='0' style='vertical-align:middle;' /> 10<img src="" style="display:none;" alt="^(" /><sup>6</sup><img src="" style="display:none;" alt=")" /> that begins with the sequence DdDddUUdDD.
</p>
<p>
What is the smallest <var>a</var><img src="" style="display:none;" alt="_(" /><sub>1</sub><img src="" style="display:none;" alt=")" /> <img src='images/symbol_gt.gif' width='10' height='10' alt='&gt;' border='0' style='vertical-align:middle;' /> 10<img src="" style="display:none;" alt="^(" /><sup>15</sup><img src="" style="display:none;" alt=")" /> that begins with the sequence "UDDDUdddDDUDDddDdDddDDUDDdUUDd"?
</p>








</div><br />
